/*
  生成由数字0～8组成的9x9矩阵，要求：
     每行都由0～8数字组成，每个数字有且仅有出现一次
     每列都由0～8数字组成，每个数字有且仅有出现一次
  TODO: 需要生成一个序列，每个元素为一个上面的矩阵，且每个矩阵中同一行相邻的两个值必须在之前的元素中未出现过
*/

#include <stdio.h>
#include <assert.h>
#include <vector>
#include <algorithm>

const int N = 9;

typedef int Trans[N][N];

std::vector<Trans*> solution;

void print(Trans* t)
{
    printf("mate:\n");
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++)
            printf("%3d", (*t)[i][k]);
        printf("\n");
    }
}

int  mate[N][N] = {0};
bool placed_line[N][N] = {false};   // place_line[i][k]==true 表示第i行已经放置数字k
bool placed_colm[N][N] = {false};   // place_colm[i][k]==true 表示第i列已经放置数字k
bool finished = false;

void place(int line, int colm)
{
    if (line >= N) {
        print(&mate);
        Trans* t = (Trans *)malloc(N*N*sizeof(int));
        for (int i = 0; i < N; i++)
            for (int k = 0; k < N; k++)
                (*t)[i][k] = mate[i][k];
        solution.push_back(t);
        finished = true;
        return;
    }
    if (colm >= N) {
        place(line + 1, 0);
        return;
    }
    if (colm == 0) {
        int v = line;
        placed_line[line][v] = true;
        placed_colm[colm][v] = true;
        mate[line][colm] = v;
        place(line, colm + 1);
        placed_line[line][v] = false;
        placed_colm[colm][v] = false;
        return;
    }
    for (int v = 0; v < N; v++) {
        // 在[line, colm]位置放置数字v
        // 数字v已经在line行
        if (placed_line[line][v]) {
            continue;
        }
        // 数字v已经在colm列
        if (placed_colm[colm][v]) {
            continue;
        }
        // 前面是否有相同的序列
        bool found = false;
        for (int i = 0; i < solution.size(); i++) {
            for (int k = 0; k < N; k++) {
                if ((*solution[i])[k][colm-1] == mate[line][colm-1] &&
                    (*solution[i])[k][colm]   == v) {
                        // printf("[%d, %d]=%d, %d\n", line, colm, v, (*solution[i])[k][colm]);
                        found = true;
                    }
            }
        }
        if (!found) {
            placed_line[line][v] = true;
            placed_colm[colm][v] = true;
            mate[line][colm] = v;
            place(line, colm + 1);
            placed_line[line][v] = false;
            placed_colm[colm][v] = false;
        }
        if (finished) {
            return;
        }
    }
}

int main()
{
    int count = 0;
    do {
        count = solution.size();
        place(0, 0);
    } while(solution.size()>count);
    for (int i = 0; i < solution.size(); i++) {
        printf("Week %d:\n", i);
        print(solution[i]);
    }
}
